package pers.sloera.leetcode.editor.cn;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 下一个更大元素 II
 *
 * @author sloera
 * @date 2022-07-24 13:00:00
 */
class NextGreaterElementIi {
    public static void main(String[] args) {
        Solution solution = new NextGreaterElementIi().new Solution();
        // int[] ints = solution.nextGreaterElements(new int[]{1, 2, 1});
        int[] ints = solution.nextGreaterElements(new int[]{1, 2, 3, 4, 3});
        System.out.println(ints);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 找寻下一个最大的数
         * <p>
         * 这种寻找下一个极值的问题，都可以用单调栈解决
         * <p>
         * 如果数字是6543217，那么对于654321，他们对应的结果都是7。就是说这中间存在重复查找。
         * 如果有一个单调栈，那当找到7的时候，只需要从这个单调栈的最后往前找，小于7的都是可以更新的
         *
         * @param nums 原始数据
         */
        public int[] nextGreaterElements(int[] nums) {
            Deque<Integer> deque = new LinkedList<>();
            int[] result = new int[nums.length];
            Arrays.fill(result, -1);
            // 因为是循环查找，所以最后一个数，要从头开始查找到前一个数，边界是2*nums.length - 1
            for (int i = 0; i < 2 * nums.length - 1; i++) {
                // 队列不为空，就一直找比当前数小的值进行更新
                while (!deque.isEmpty() && nums[deque.peek()] < nums[i % nums.length]) {
                    result[deque.pop()] = nums[i % nums.length];
                }
                // 队列为空，或者比当前数值大了，就添加到队列里面
                deque.push(i % nums.length);
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
